/**
 * NOTE: 红黑树:
 *  1. 二分搜索树, 每个节点红色或者是黑色
 *  2. root 是黑色
 *  3. 叶子叶节点(最后的空节点) 是黑色
 *  4. 如果一个节点是红色的, 那么他的孩子节点都是黑色
 *  5. 任意一个节点到叶子节点, 经过的黑色节点是一样的， 黑平衡
 *  6. 所有的红色节都是向左倾斜, 在左子树上, 就是 红色节点要么在左子树上， 要么在右子树上；
 *  红黑树是保持 "黑平衡" 的二叉树, 左右子树的黑色节点是平衡的, 高度差不超过 1
 *
 * NOTE: 最大的高度(2logN), 不会退化成为链表, [添加] 元素 和 [删除] 元素比较高效, 但是 [查询] 略低于 AVL 性能
 */

/**
 * NOTE: 2-3 树;
 * 理解 2-3 树 对于理解红黑树, 理解 b 类树有指导的意义
 * 满足二分搜索树的基本性质
 * 节点可以存放一个元素或者是存放两个元素
 *  a      a b
 * / \    / | \
 * 1 元素存在两个孩子叫做 2 节点
 * 2 元素存放 3 个孩子的叫做 3 节点,
 * 2-3 树是一颗绝对平衡的树
 * 添加节点绝对不会添加到一个空的位置, 会与之前的孩子节点进行融合,
 * 当融合到 4 节点时, 会进行分裂, 形成二分搜索树, 当分裂出现不平衡的情况, 那么会向上进行融合变为 3 节点
 */

/*
  所谓的红色的节点是和父节点融合在一起的, 红色的节点才需要向上与父节点进行融合
 */

import { LinedListQueue } from 'data-structure/linkedList/LinkedListQueue'
import { LinkedListStack } from 'data-structure/linkedList/LinkedListStack'

export interface MapTreeNodeInter<V = any> {
  key: number | string
  value: V
  left: RBTreeNode<V> | null,
  right: RBTreeNode<V> | null,
}

// 存在映射版本
export class RBTreeNode<V = any> implements MapTreeNodeInter<V> {
  // interface
  public key!: number | string
  public value!: V
  public left: RBTreeNode<V> | null = null
  public right: RBTreeNode<V> | null = null
  public color: boolean = true
  public count: number = 1
  // 该元素在那一层
  public depth: number = 0
  // 以该元素为根的树有多少个元素
  public size: number = 0
  constructor(key: number | string, value: V) {
    this.key = key
    this.value = value
  }
}

/**
 * 二分搜索树, 存储的数据必须要有可比较性
 * 1. 一个二叉树,
 * 2. 每一个节点的值: 大于其左子树的所有的值, 小于其右子树的所有的值
 * 3. 每一颗子树都是二分搜索树
 */
export class RedBlackTree<V = any> {
  private static RED = true
  private static BLACK = false
  private root!: RBTreeNode<V>
  private size: number = 0
  constructor(root?: RBTreeNode<V>) {
    this.root = root!
    if (root) {
      this.size = 1
    }
  }

  /**
   * isEmpty
   */
  public isEmpty() {
    return this.size === 0
  }

  /**
   * floor: 寻找前驱
   */
  public floor() {
    // TODO: todo
  }

  /**
   * ceil: 寻找后继
   */
  public ceil() {
    // TODO: todo
  }

  /**
   * rank: 元素的排名
   */
  public rank() {
    // TODO: todo
  }

  /**
   * select: 根据排名来查找元素
   */
  public select() {
    // TODO: todo
  }

  /**
   * getRoot
   */
  public getRoot() {
    return this.root
  }

  /**
   * add:
   * 2-3 树中添加 一个新的元素 , 或者添加到 2- 节点, 形成一个3-节点,
   * 或者添加 进入到 3- 节点, 暂时形成一个 4- 节点, 永远添加红色节点
   */
  public add(newNode: RBTreeNode<V>) {
    this.root = this.addNode(this.root, newNode)
    this.root.color = RedBlackTree.BLACK // 最终的根节点为黑
  }

  /**
   * removeMaxNode: 删除最大值的节点
   */
  public removeMax(): RBTreeNode<V> {
    let node = this.maximum()

    // 删除以 root 为根节点的树中删除 node
    this.root = this.removeMaxTreeNode(this.root)

    return node
  }

  /**
   * removeMinNode: 删除最小值的节点
   */
  public removeMin(): RBTreeNode<V> {
    let node = this.minimum()

    // 删除以 root 为根节点的树中删除 node
    this.root = this.removeMinTreeNode(this.root)

    return node
  }

  /**
   * remove: 删除任意的元素
   */
  public remove(node: RBTreeNode<V>) {
    this.root = this.removeTreeNode(this.root, node) as RBTreeNode
  }

  /**
   * minimum: 查找最小元素
   */
  public minimum(): RBTreeNode<V> {
    return this.minimunTree(this.root)
  }

  /**
   * maximum: 查找最大元素
   */
  public maximum(): RBTreeNode<V> {
    return this.maximunTree(this.root)
  }

  /**
   * levelOrder: 层序遍历: (广度优先遍历: 更快的查找到对应的元素)
   */
  public levelOrder(cb: (node: RBTreeNode<V> | null) => void) {
    const q = new LinedListQueue<RBTreeNode<V>>()
    q.enqueue(this.root)
    while (!q.isEmpty()) {
      let cur = q.dequeue()
      cb(cur)
      if (cur.left) {
        q.enqueue(cur.left)
      }
      if (cur.right) {
        q.enqueue(cur.right)
      }
    }
  }

  /**
   * getSize
   */
  public getSize() {
    return this.size
  }

  /**
   * set: 更新节点的值
   */
  public set(key: number | string, value: V) {
    let node = this.query(key)
    if (node) {
      node.value = value
      return
    }
    this.add(new RBTreeNode(key, value))
  }

  /**
   * get
   */
  public get(key: number | string): V | undefined {
    if (!this.root) {
      return undefined
    }
    let node = this.query(key)
    if (!node) {
      return undefined
    }
    return node.value
  }

  /**
   * query
   */
  public query(key: number | string): RBTreeNode<V> | null {
    if (!this.root) {
      return null
    }
    const stack = new LinkedListStack<RBTreeNode>()
    stack.push(this.root)
    while (!stack.isEmpty()) {
      let node = stack.pop()
      if (key === node.key) {
        return node
      }
      if (node.right) {
        stack.push(node.right)
      }
      if (node.left) {
        stack.push(node.left)
      }
    }
    return null
  }

  /**
   * isBST: 是否是一颗二叉树, 性质, 使用中序排序的时候是一个顺序的序列
   */
  public isBST(): boolean {
    let keys: string[] = []
    this.inOrderRecursion(keys)
    console.log(keys)
    let isBST = true
    for (let i = 1; i < keys.length; i++) {
      if (keys[i - 1] > keys[i]) {
        isBST = false
      }
    }
    return isBST
  }

  /**
   *  preorder: 深度优先遍历[前序遍历(递归)];
   */
  public preOrderRecursion(cb: (node: RBTreeNode<V> | null) => void) {
    this.preOrderTreeRecursion(this.root, cb)
  }

  /**
   * preorder: 非递归的实现
   */
  public preOrder(cb: (node: RBTreeNode<V> | null) => void) {
    if (!this.root) {
      return
    }
    const stack = new LinkedListStack<RBTreeNode>()
    stack.push(this.root)
    while (!stack.isEmpty()) {
      let node = stack.pop()
      cb(node)
      if (node.right) {
        stack.push(node.right)
      }
      if (node.left) {
        stack.push(node.left)
      }
    }
  }

  /**
   * inOrder: 深度优先遍历: [中序遍历(递归实现)] 得到的结果是一个有序的序列,
   */
  public inOrderRecursion(keys?: Array<string | number>) {
    this.inOrderTreeRecursion(this.root, keys)
  }

  /**
   * postOrderRecursion: 深度优先遍历: 后序遍历(递归实现)
   */
  public postOrderRecursion(cb: (node: RBTreeNode<V> | null) => void) {
    this.postOrderTreeRecursion(this.root, cb)
  }

  /**
   * contains
   */
  public contains(key: string | number): boolean {
    return this.containsNode(this.root, key)
  }

  /**
   * isRed
   */
  public isRed(node: RBTreeNode<V>): boolean {
    if (!node) {
      return RedBlackTree.BLACK
    }
    return node.color
  }

  //   node                     x
  //  /   \     左旋转         /  \
  // T1   x   --------->   node   T3
  //     / \              /   \
  //    T2 T3            T1   T2
  private leftRotate(node: RBTreeNode<V>): RBTreeNode<V> {
    let x = node.right as RBTreeNode
    // 左旋转
    node.right = x.left
    x.left = node
    x.color = node.color
    node.color = RedBlackTree.RED
    return x
  }

  //        node                     x
  //       /   \     右旋转         /  \
  //      x    T1   --------->    T3  node
  //     / \                         /   \
  //   T2  T3                       T1   T2
  // let x = node.left as RBTreeNode
  // node.left = x.right
  // x.right = node
  private rightRotate(node: RBTreeNode<V>): RBTreeNode<V> {
    let x = node.left as RBTreeNode
    node.left = x.right
    x.right = node
    x.color = node.color
    node.color = RedBlackTree.RED
    return x
  }

  // 颜色反转
  private flipColors(node: RBTreeNode<V>) {
    node.color = RedBlackTree.RED
    node.left!.color = RedBlackTree.BLACK
    node.right!.color = RedBlackTree.BLACK
  }

  private removeTreeNode(node: RBTreeNode<V>, delNode: RBTreeNode<V>): RBTreeNode<V> | null | void {
    // 没有该节点
    if (!node) {
      return null
    }
    let ret: RBTreeNode<V>
    if (node.key > delNode.key) { // 在左子树
      node.left = this.removeTreeNode(node.left!, delNode) as RBTreeNode
      ret = node
    } else if (node.key < delNode.key) { // 在右子树
      node.right = this.removeTreeNode(node.right!, delNode) as RBTreeNode
      ret = node
    } else { // 找到了对应的节点
      this.size--
      if (!node.left) {
        let right = node.right
        node.right = null
        ret = right as RBTreeNode<V>
      } else if (!node.right) {
        let left = node.left
        node.left = null
        ret = left as RBTreeNode<V>
      } else {
        // 左右子树都存在的话, 需找到当前节点的后继中
        let min = this.minimunTree(node.right!)
        // 这里进行了 size--; 实际上这里是寻找子树的新的根节点
        min.right = this.removeTreeNode(node.right!, min) as RBTreeNode<V>
        // 所以这里要 size++
        min.left = node.left
        node.left = node.right = null
        ret = min
      }
    }

    if (!ret) {
      return null
    }
    // 这里已经向上回溯到根节点
    // 无论是在左子树或者是右字数添加节点, 高度都会变化, 更新 height, 因为左右子树的高度之差小于等于 1
    return ret
  }

  private removeMaxTreeNode(node: RBTreeNode<V>): RBTreeNode<V> {
    if (!node.right) {
      let left = node.left
      node.left = null
      this.size--
      return left!
    }
    node.right = this.removeMaxTreeNode(node.right)
    return node
  }

  // 删除: node, 放回删除节点后的新的树
  private removeMinTreeNode(node: RBTreeNode<V>): RBTreeNode<V> {
    if (!node.left) {
      let right = node.right
      node.right = null
      this.size--
      return right!
    }
    node.left = this.removeMinTreeNode(node.left)
    return node
  }

  private minimunTree(node: RBTreeNode<V>): RBTreeNode<V> {
    if (!node.left) {
      return node
    }
    return this.minimunTree(node.left)
  }

  private maximunTree(node: RBTreeNode<V>): RBTreeNode<V> {
    if (!node.right) {
      return node
    }
    return this.maximunTree(node.right)
  }

  private postOrderTreeRecursion(node: RBTreeNode<V>, cb: (node: RBTreeNode<V> | null) => void) {
    if (!node) {
      cb(null)
      return
    }
    this.postOrderTreeRecursion(node.left!, cb)
    this.postOrderTreeRecursion(node.right!, cb)
    cb(node)
  }

  private inOrderTreeRecursion(node: RBTreeNode<V>, keys?: Array<string | number>) {
    if (!node) {
      return
    }

    this.inOrderTreeRecursion(node.left!, keys)
    if (keys) {
      keys.push(node.key)
    }
    this.inOrderTreeRecursion(node.right!, keys)
  }

  private preOrderTreeRecursion(node: RBTreeNode<V>, cb: (node: RBTreeNode<V> | null) => void) {
    if (!node) {
      return cb(null)
    }
    cb(node)
    this.preOrderTreeRecursion(node.left!, cb)
    this.preOrderTreeRecursion(node.right!, cb)
  }

  private containsNode(node: RBTreeNode<V>, key: string | number): boolean {
    if (!node) {
      return false
    }
    if (node.key > key) { // 左子树
      return this.containsNode(node.left!, key)
    } else if (node.key < key) { // 右子树
      return this.containsNode(node.right!, key)
    }
    return true
  }

  // 向以node为根的红黑树中插入元素，递归算法
  // 返回插入新节点后红黑树的根
  private addNode(node: RBTreeNode<V>, newNode: RBTreeNode<V>): RBTreeNode<V> {
    if (!node) {
      this.size++
      return newNode // 默认插入红色节点
    }
    if (node.key < newNode.key) { // 大于当前根节点
      node.right = this.addNode(node.right!, newNode)
    } else if (node.key > newNode.key) { // 小于
      node.left = this.addNode(node.left!, newNode)
    } else { // 等于
      node.value = newNode.value
    }

    // 添加节点后回溯向上, 维护红黑树的性质

    // 当前节点的 右孩子是红, 左孩子不是红
    if (this.isRed(node.right!) && !this.isRed(node.left!)) {
      node = this.leftRotate(node)
    }

    // 当前节点的左孩子 是红色, 左孩子的左孩子是红色
    if (this.isRed(node.left!) && this.isRed(node.left!.left!)) {
      node = this.rightRotate(node)
    }

    // 左右孩子都是红色, 需要反转颜色
    if (this.isRed(node.left!) && this.isRed(node.right!)) {
      this.flipColors(node)
    }

    // 三种情况不是互斥的
    return node
  }
}

/**
 * 红黑树: 对于完全随机的 数据, 普通 的 二分搜索 树很好用, 缺点是在极端的情况下会退化为链表,
 * 对于查询多的使用情况下, AVL 树好用
 * 红黑树牺牲了平衡性
 * 在统计性能更优的是红黑树(综合增删改查的操作)
 * 二分搜索树是有序的
 *
 * 保持黑平衡, 与 2-3 树的关系; 左倾的红黑树或者是右倾的红黑树
 */

/**
 * 伸展树(Splay Tree): 局部性的原理: 刚被访问的内容下次高概率被再次访问,
 * java 中的: TreeMap, TreeSet 是基于红黑树实现
 */
